Cryptography is used in applications that require secure transmission and storage of data. Secure transmission is needed between computers, telephones, facsimile machines, sensors, and other devices. Secure storage is required for memories, disks, and tapes. In all cases, the principal goal of cryptography is to prevent unauthorized access to the data.
Generally, cryptography uses two types of keys and corresponding protocols: symmetric and asymmetric. In symmetric cryptography, the identical key is used for encrypting and decrypting. In this case, both the encryptor and decryptor know the key. Because symmetric cryptography relies on the secrecy of the key, the key can be comparatively small, e.g., 128 bits or smaller. Symmetric protocols are relatively fast and easy to implement. The main problem with symmetric cryptography is to provide a secure mechanism for key exchange, which is always subject to attack by adversaries.
In asymmetric cryptography, a public key is used for encrypting and a private key is used for decrypting. The security of public cryptography relies on the difficulty of deriving the private key from the public key. Therefore, the public key must be comparatively large, e.g., 1024 bits or more.
The computational complexity and power consumption of asymmetric cryptography is several orders of magnitude greater than that for symmetric cryptography. Therefore, asymmetric cryptography is problematic for small, battery operated and reduced functionality devices (RFDs), such as personal digital assistants (PDAs), laptops, cellular telephones, and wireless environment sensors. In addition, because public keys are available to imposters, authentication is required.
Protocols for authenticating key exchange communications are described by Needham and Schroeder, “Using encryption of authentication in large networks of computers,” Communications of the ACM, 21(12), pp. 993-999, December 1978. In the Needham-Schroeder protocol, an authenticator (A) authenticates a master device (M) and a slave device (S) using a master key (MK), a slave key (SK), and a symmetric protocol. An encryption of a message X with key K is denoted by X{K}.
The exchanges of the symmetric Needham-Schroeder key exchange protocol use the following messages:
(1)M → AM, S, RM(2)A → M{RM, S, MK, {MK, M}{SK}}{MK}(3)M → S{MK, M}{SK}(4)S → M{RS}{MK}(5)M → S{RS − 1}{MK}
In the first message (1), the master device M contacts the authenticator A to request a master key MK for a slave device S. The message includes a random number RM to protect against replay attacks.
The authenticator A replies with a message (2) that includes the random number RM, the slave device identifier S, the master key MK and a ‘ticket’ {MK, M}{SK}, which includes the master key MK and the master device identifier M. The ticket is encrypted with the slave key SK. The entire message (2) is encrypted with the master key MK. The master device M decrypts the message (2), stores the master key MK, and forwards the ticket to the slave device S in message (3). The ticket is encrypted with the slave key SK.
On receipt of the ticket, the slave device decrypts the ticket using the slave key SK, and stores the master key. In the fourth message, the slave device sends a random number RS encrypted with the master key MK to the master device. In response, in message (5), the master device M sends the random number with RS−1 encrypted with the master key. The fourth and fifth messages also prevent replay attacks.
The Needham-Schroeder protocol for authentication is not secure because it can be subject to attacks by imposters, Yu, et al., “The perils of unauthenticated encryption: Kerberos 4,” Proceedings of Network and Distributed System Security Symposium, NDSS '04, February 2004.
Another prior art authentication system used in fixed infrastructure networks, is based on the Needham-Schroeder key exchange protocol, see, Neuman, et al., “Kerberos: An authentication service for computer networks,” IEEE Communications Magazine, 32(9): pp. 33-38, September 1994. That method also relies in previously established keys between users of the system.
Pirzada et al., describe an authentication system for mobile ad hoc networks, Pirzada, et al., “Kerberos assisted authentication in mobile ad hoc networks,” Proceedings of the 27th Australasian Computer Conference, January, 2004.
A transient association authentication method in sensor networks and a security policy for execution of an authentication method is described by Stajano et al., “The resurrecting duckling: Security issues for ubiquitous computing,” IEEE Computer Magazine, 35(4), pp. 22-26, April 2002. There, master keys are imprinted on devices using either an out-of-band communication mechanism, if it is available, or by transmitting the master keys using a wireless medium. The latter method is vulnerable to an adversary that is eavesdropping on the medium. In that policy, a device recognizes a master as an owner of the key that was imprinted on the device, which makes the system vulnerable to an imposter that imprints a key prior to the owner having access to the device. The resurrecting duckling is well-suited for environments where the owner of the devices does not have on-line access. However, it desired to provide a secure environment for networked sensors where the owner does have on-line access.
The SPINS suite of security protocols for sensor networks described by Perrig et al., “Spins: Security protocols for sensor networks,” Journal of Wireless Networks, 8(5), pp. 521-534, September 2002. In SPINS, keys are shared between sensors and a base stations. However, SPINS does not describe how the keys are exchanged in the first place.
Therefore, it is desired to provide an authenticated key exchange method that overcomes the problems of the prior art.